Field of the Invention
The present invention relates to a decoding system for decoding variable-length-encoded data, and more particularly, to a method and apparatus for decoding run-level-encoded symbols using a scan pattern selected from various scan patterns.
Recently, various methods for encoding image and audio signals into digital data so as to be transmitted or stored in a storing medium, and decoding the encoded digital data in order to be reproduced, have been used in a system for transmitting and receiving image and audio signals. However, there is needed a technique for further reducing the quantity of transmission data in order to enhance data transmission efficiency in the encoding and decoding system. There have been a transformation encoding method, a differential pulse code modulation (DPCM) method, a vector quantization method, and a variable-length-coding method, etc., as methods for coding the digital data to be transmitted or stored. The encoding methods remove redundant data contained in the digital data to be transmitted or stored, to further reduce a total quantity of data.
The image data of each frame is divided into blocks of a predetermined size, and data-processed in an encoding and decoding system in order to store, transmit or receive the image signals. Each block data or differential data between block data is orthogonal-transformed, so that the image data is transformed into transformation coefficients in a frequency domain. There have been discrete cosine transform (DCT), Walsh-Hadamard transform (WHT), discrete Fourier transform (DFT), and discrete sine transform (DST), etc., as well-known block data transformation methods. The transformation coefficients obtained by these transformation methods are properly quantized and variable length-encoded according to the characteristics of coefficient data, so that compression efficiency is increased. Since human visual perception is more sensitive to low frequency than high frequency, the high-frequency component data is reduced by data processing. Accordingly, the quantity of the encoded data can be decreased.
The apparatus for variable-length-coding compresses data based on the probability of occurrence of the symbols, and includes a variable-length-coding table for variable-length-encoding input symbols. The variable-length-coding table is designed according to the Huffman coding technique. As is well known, the Huffman coding allocates different codes which vary in length according to the probabilities of occurrence of predetermined symbols. That is, the higher the probability is, the shorter the code which is allocated, and the lower the probability is, the longer the code which is allocated.
In the existing encoding system, the symbols input to the variable-length-coding apparatus are [run, level] symbols obtained via run-level-coding. In the case of the MPEG standard of image standardization, image data divided into blocks each having an 8.times.8 pixel size is transformed into data in the frequency domain and then quantized. The quantized transformation coefficients are expressed in a two-dimensional frequency domain of an 8.times.8 size, and encoded into [run, level] symbols by a well-known zigzag scan for scanning from low frequency to high frequency in the two-dimensional frequency domain. Here, the "run" means the number of times of occurrence of zero between coefficients not "0", and the "level" means an absolute value of a coefficient not "0". In the case of a frequency domain of an 8.times.8 size, the run can have values from "0" to "63". In the case that the quantized transformation coefficients are an integer value from -255 to 255, the level can have values from 1 to 255, and the sign is separately indicated.
The use of a zigzag scan pattern is due to a phenomenon that energies of the image signal are concentrated at the low frequency domain centering around the DC component. However, the energy of the image signal can be more concentratively or more widely distributed to frequency components of a horizontal orientation or a vertical orientation according to the pattern of the image signal. Therefore, the existing zigzag scan pattern is not always the optimum scan pattern for variable-length-coding the image data. Thus, scan patterns which can be adaptably sloped to a horizontal orientation or a vertical orientation in the two-dimensional frequency domain according to distribution characteristics of the image data, are desirable for the variable-length encoding and decoding. The relevant prior art is disclosed in U.S. Pat. No. 5,497,153 entitled "Variable-Length Coding and Decoding System", which is assigned to the same assignee as that of the present invention.
According to the above prior art reference, the digital data divided into blocks each having a predetermined size is variable-length-encoded according to various scan patterns, the length of the variable-length-encoded data is accumulated in correspondence to each scan pattern, and then a scan pattern corresponding to the minimum accumulated length is selected. Both the selected scan pattern and the variable-length-encoded data corresponding to the selected scan pattern are transmitted. When decoding, the transmitted variable-length-encoded data is scanned according to the same scan pattern as selected when variable-length-encoding and is variable-length-decoded. Thus, a data compression efficiency is further enhanced by using an optimized scan pattern for variable-length-encoding and variable-length-decoding the block data. The variable-length-decoding apparatus disclosed in the above prior art will be described with reference to FIG. 1.
FIG. 1 shows an example of a conventional variable-length-decoding apparatus. Referring to FIG. 1, variable-length-encoded data D.sub.VLC and corresponding scan pattern data D.sub.SCAN transmitted from an encoding apparatus (not shown) are input to a variable-length-decoder 11 and a scan pattern selector 12, respectively. The variable-length-decoder 11 converts the input variable-length-encoded data D.sub.VLC into a [run, level] symbol according to a variable-length-decoding table. The scan pattern selector 12 which stores scan addresses according to various scan patterns of 1 through N in correspondence to each scan pattern, selects scan addresses ADDRs corresponding to the input scan pattern data D.sub.SCAN to output the selected result. A run-level-decoder 13 transforms the [run, level] symbols input from the variable-length-decoder 11 into quantization coefficients expressed in the two-dimensional spatial domain according to the corresponding scan addresses ADDRs input from the scan pattern selector 12. Then, the quantization coefficients are supplied to an inverse quantizer (not shown).